package class25_单调栈结构.test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 问题：给定一个数组请找出数组元素左，右两边最小的元素
 * 单调栈
 */
public class Code01_MonotonousStack {
    /**
     * 没有重复的数组
     * @param arr
     * @return
     */
    public static int[][] getNearLessNoRepeat(int[] arr){
        int[][] res = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while(!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                Integer value = stack.pop();
                int leftValue = stack.isEmpty()?-1: stack.peek();
                res[value][0] = leftValue;
                res[value][1] = i;
            }
            stack.push(arr[i]);
        }
        while (!stack.isEmpty()){
          int value = stack.pop();
          int left = stack.isEmpty()?-1:stack.peek();
          res[value][0] = left;
          res[value][1] = -1;
        }
        return res;
    }

    /**
     * 可以重复的数组
     * @return
     */
    public static int[][] getNearLess(int[] arr){
        int[][] res = new int[arr.length][2];
        Stack<List<Integer>> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek().get(0)]>arr[i]){
                List<Integer> pop = stack.pop();
                int leftIndex = stack.isEmpty()?-1:stack.peek().get(0);
                for (int j = 0; j < pop.size(); j++) {
                    res[pop.get(j)][0] = leftIndex;
                    res[pop.get(j)][1] = i;
                }
            }
            //入栈
            if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){//栈中已经存在
                List<Integer> pop = stack.pop();
                pop.add(i);
                stack.push(pop);
            }else {
                ArrayList<Integer> push = new ArrayList<>();
                push.add(i);
                stack.push(push);
            }
        }
        while (!stack.isEmpty()){
            List<Integer> pop = stack.pop();
            int leftIndex = stack.isEmpty()?-1:stack.peek().get(0);
            for (int i = 0; i < pop.size(); i++) {
                res[pop.get(0)][0] = leftIndex;
                res[pop.get(0)][1] = -1;
            }
        }
        return res;
    }

}
